This version adds explicit variable definitions and inline comments. The visualization uses the same graph and color scheme as “DFS—Core Idea”.

  • Variables defined up front: visited, parent, d, f, and a global time counter.
  • Pre-order action: set visited[u], record d[u] when entering DFS-Visit(u).
  • Post-order action: record f[u] after exploring all neighbors.
  • Visualization states unified: Active, Visited, Unvisited (finished nodes remain “visited”).
  • Example graph matches Slide 17 to keep the mental model consistent.

DFS(G):
# Initialize per-vertex state
for v in V(G):
visited[v] ← false; parent[v] ← NIL; d[v] ← NIL; f[v] ← NIL
# Global timestamp for discovery/finish
time ← 0
# Visit every component (graph may be disconnected)
for s in V(G):
if not visited[s]:
DFS-Visit(s)

DFS-Visit(u):
# Pre-order: mark visited and record discovery time
visited[u] ← true
d[u] ← ++time
# Explore each neighbor of u
for w in G[u]:
if not visited[w]:
parent[w] ← u
DFS-Visit(w)
# Post-order: record finish time after all descendants
f[u] ← ++time